public class test {
    public class test {
        // leetcode 322.零钱兑换
        class Solution {
            // 二维解法 -> 完全背包
            public int coinChange1(int[] coins, int amount) {
                // 1. 创建dp表
                int n = coins.length;
                // 代表访问到第 i 个硬币时,价值正好为 j 的最小硬币个数
                int[][] dp = new int[n + 1][amount + 1];
                // 2. 初始化
                int max = amount + 10;
                // 都变为最大值,当值为max时不合法.
                for (int i = 1; i <= amount; i++) {
                    dp[0][i] = max;
                }
                dp[0][0] = 0;
                // 3. 填表
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= amount; j++) {
                        dp[i][j] = dp[i - 1][j];
                        if (j >= coins[i - 1]) {
                            dp[i][j] = Math.min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
                        }
                    }
                }
                // 4. 返回值
                return dp[n][amount] != max ? dp[n][amount] : -1;
            }

            // 一维解法 -> 空间优化
            public int coinChange(int[] coins, int amount) {
                // 1. 创建dp表
                int n = coins.length;
                // 代表访问到第 i 个硬币时,价值正好为 j 的最小硬币个数
                int[] dp = new int[amount + 1];
                // 2. 初始化
                int max = amount + 10;
                // 都变为最大值,当值为max时不合法.
                for (int i = 1; i <= amount; i++) {
                    dp[i] = max;
                }
                // 3. 填表
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= amount; j++) {
                        if (j >= coins[i - 1]) {
                            dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);
                        }
                    }
                }
                // 4. 返回值
                return dp[amount] != max ? dp[amount] : -1;
            }
        }
        // leetcode 518.零钱兑换Ⅱ
        class Solution {
            public int change(int amount, int[] coins) {
                // 1. 创建 dp 表
                int n = coins.length;
                //当访问到第 i 个硬币时,价值正好为 j 的情况个数
                int[] dp = new int[amount+1];
                // 2. 初始化
                dp[0] = 1;
                // 3. 填表
                for(int i = 1;i <= n;i++){
                    for(int j = 0;j <= amount;j++){
                        if(j >= coins[i - 1]){
                            dp[j] += dp[j - coins[i - 1]];
                        }
                    }
                }
                // 4. 返回值
                return dp[amount];
            }
        }
    }
}
